; Modified multiplicative congruential pseudorandom number generator
;
; Written by Pedro Gimeno Fortea, donated to the public domain.
;
; This generator is the same used in the ZX81 and the ZX Spectrum, but
; it's faster because it doesn't use the calculator routines.
;
; 75 is a primitive root modulo 65537, which is a prime. So, given X > 0,
; this sequence:
;    X <- X*75 mod 65537
; iterates through all values from 1 to 65536 in a random-looking order
; (multiplicative congruential generator). Vickers' trick to shift the range
; to 0-65535 and stay within a 16 bit machine word was to modify it to:
;    X <- ((X+1)*75-1) mod 65537
; That gives a number in the range of a machine word, and it can't generate
; 65536. That expression can be simplified to
;    X <- (X*75 + 74) mod 65537
; which is what is used here.
;
; The modulo 65537 is performed as (X & 0xFFFF) - (X >> 16), then adding 1 if
; the result is negative. This method can be derived as follows:
;    a*65537 mod 65537 = 0 (because a*65537 is a multiple of 65537)
;    a*(65536 + 1) mod 65537 = 0
;    (a*65536 + a) mod 65537 = 0
; Subtracting a from both sides (before the mod):
;    a*65536 mod 65537 = (-a) mod 65537
; Adding b to both sides (before the mod):
;    (a*65536 + b) mod 65537 = (b - a) mod 65537
; Let a = floor(x/65536), b = x mod 65536, so that x = a*65536 + b; then:
;    x mod 65537 = (b - a) mod 65537
; When b - a >= 0, the modulo is b - a because b < 65536.
; When b - a < 0, assuming a < 65536, the modulo is b - a + 65537. Since
; b - a is internally represented as b - a + 65536 in 16-bit twos complement,
; just adding 1 gives the correct value of the modulo.

; This routine trashes all regular registers; feel free to add push and pop
; instructions as necessary before using. It modifies SEED and returns the
; new value of SEED in HL (which is the new random number).
; The core calculation (everything except the retrieval/storage of SEED and
; the final RET) takes 210 cycles.

prng:		ld	hl,(SEED)	; current seed
		; HL = (HL * 75 + 74) % 65537
		ld	b,h
		ld	c,l
		xor	a
		ld	de,74
		add	hl,hl		; *2
		adc	a,a
		add	hl,hl		; *4
		adc	a,a
		add	hl,hl		; *8
		adc	a,a
		add	hl,bc		; *9
		adc	a,d
		add	hl,hl		; *18
		adc	a,a
		add	hl,hl		; *36
		adc	a,a
		add	hl,bc		; *37
		adc	a,d
		add	hl,hl		; *74
		adc	a,a
		add	hl,bc		; *75
		adc	a,d
		add	hl,de		; +74
		adc	a,d		; guaranteed no carry
		ld	e,a
		sbc	hl,de		; % 65537
		ld	e,d
		adc	hl,de		; add carry for final modulo
		ld	(SEED),hl	; new seed
		ret
